"""
PyTris - a tic-tac-toe library for Python
Copyright (c) 2009 Edoardo Spadolini <kerio00@gmail.com>

This library is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or any
later version.

This library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.

All functions in this library expect the board to be a 9 element list
or tuple or whatever subscriptable you can think of (must support
iteration and slice assignment), with 1 and -1 as the players, and 0
as the empty space.

e.g.: [0, 0, 1, 1, -1, 0, 0, 0, 1] translates to    |   | X
                                                 ---+---+---
                                                  X | O |
                                                 ---+---+---
                                                    |   | X

This choice was made because this way it's very easy to switch between
players, or to operate with the whole board via mathematical
operations.
"""

import random

# using slices is better because then you can access the row via
# board[row], instead of board[x] for x in row
rows = (slice(0, 3, 1), slice(3, 6, 1), slice(6, 9, 1), # horizontal
        slice(0, 7, 3), slice(1, 8, 3), slice(2, 9, 3), # vertical
        slice(0, 9, 4), slice(2, 7, 2)) # diagonal

# rows to check for each cell
cell_rows = {0: (0, 3, 6), 1: (0, 4), 2: (0, 5, 7),
             3: (1, 3), 4: (1, 4, 6, 7), 5: (1, 5),
             6: (2, 3, 7), 7: (2, 4), 8: (2, 5, 6),
             None: (0, 1, 2, 3, 4, 5, 6, 7)}

def winning(board, lastmove=None):
    """
    Returns 1, -1, 0 according to the winning player in the
    board. Does not make assumptions about the future of the game;
    only checks for horizontal, vertical and diagonal rows, 0 is
    returned in the event of a tie.  If lastmove is specified, it only
    checks the rows passing by that cell.
    """
    for i in cell_rows[lastmove]:
        row = board[rows[i]]
        if 0 not in row:
            if -1 not in row: return 1
            elif 1 not in row: return -1
    else:
        return 0

def boardvalue(board, move, player, alpha=1, beta=-1):
    """
    Returns the value of board and move according to player. board
    must be a list (edited and reverted). move is the id of the move
    the player is supposed to perform, alpha and beta are for internal
    use.
    """
    board[move] = player # make the move
    win = winning(board, move)
    if 0 not in board or win:
        board[move] = 0 # reverts the move
        return win * player # subjective to player
    else:
        for foe_move in range(9):
            if board[foe_move]: continue # the cell is not free
            # NegaMax magic... :)
            movevalue = -boardvalue(board, foe_move, -player, -beta, -alpha)
            if movevalue < alpha: # expecting the worst
                alpha = movevalue
                if movevalue <= beta: break # alpha-beta cutoff
        board[move] = 0 # reverts the move
        return alpha

def ai_negamax(board, player):
    """
    Returns one of the optimal moves given a board status and a
    player.  Uses NegaMax for the calculations. board must be a list.
    """
    board = list(board) # a copy, to preserve it during the elaboration
    value, moves = -1, []
    for move in range(9):
        if board[move]: continue # the cell is not free
        movevalue = boardvalue(board, move, player)
        if movevalue > value:
            value = movevalue
            moves = [move]
        elif movevalue == value:
            moves.append(move)
    
    return random.choice(moves)

def _test():
    """
    Testing unit, kinda - I figure 10000 games is enough to spot
    errors in the negamax ai; others can't be tested without human
    intervention.
    """
    ai_random = lambda b, p: random.choice([x for x in range(9) if not b[x]])
    players = {-1: ai_random, 1: ai_negamax}
    for i in range(10000):
        board = [0] * 9
        player = 1
        while winning(board) == None:
            board[players[player](board, player)] = player
            player = -player
        else:
            if winning(board) != 0:
                print("ERROR", i)
                print(board)
                break
            else:
                print("OK", i)

if __name__ == '__main__':
    _test()
